#ifndef PRIME_H
#define PRIME_H

// #include <cmath>
#include <iostream>
using namespace std;

/** # 质数
 * ## 质数的定义：大于 1 的自然数，除了自身和 1，不能被其他自然数整除的数
 * ## 质数的意义：
 * ### 密码学：
 * 现代密码学（非对称密码）中的加密、解密过程都依赖质数
 * - 如 RSA 算法依赖两个大质数的乘积生成公钥和私钥
 * ### 机械设计：
 * 齿轮的设计通常采用质数 5 7 11 13 ...
 * - 保证了两个齿轮最大公约数为 1 使得运行过程中任意两齿都能互相啮合
 * - 更好地磨合：由于硬度、误差、材质等原因，刚出厂的齿轮是需要一段时间磨合的
 * - 每个齿都能互相磨合，磨损过程更均匀、减少震动、延长使用寿命。
 * ### 数据传输与校验：
 * 密码学中的数字签名算法（数字签名，私钥加密公钥解密）
 * - 数字签名可验证文件完整性，确保数据未被破坏或篡改
 * - 数字签名应用：网站安全证书、电子合同、数字货币
 * 身份证号的校验：
 * - 身份证号结构：共 18 位
 * - 前 6 位：地区
 * - 第 7~14 位：出生日期
 * - 第 15~17 位：顺序码，17 位可表示出生性别（奇数为男，偶数为女）
 * - 第 18 位：校验码
 * 身份证校验算法：
 * a. 前 17 位数分别乘 17 个系数并求和，
 * b. 结果 a 对 11 取余
 * c. 12 减结果 b
 * d. 结果 c 对 11 取余 == 第 18 位
 * - 17 个系数分别为 7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2
 * - 若根据前 17 位数字计算出的校验码与第 18 位数字不同，即表示这个身份证号填错了。
 * - 有许多实名认证系统、网络报名系统，都根据这一原理验证用户是否正确填写了身份证号。
 * - 11 是质数，且与 17 个系数均互质，可保证即使某两位数写反了，也能校验出身份证号填写错误。
 * - 同时，对 11 取余后，一共有 0~10 十一个结果，10 用罗马数字 X 表示，可恰好使身份证号长度为 18 位数字。
 * ### 数学研究：未解之谜如：质数分布规律、质数定理（公式）
 */

// 我的身份证号
// int csz[18] = {5, 0, 0, 2, 2, 6, 2, 0, 0, 0, 0, 6, 0, 7, 1, 5, 1, 2};
// bool isValidID(int id[18]) {
//   int k[17] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
//   // id[17] = (12 - (sum(k[i] * n[i]) % 11)) % 11;
// }

/** 判断一个数是否为质数
 * @fn isPrime
 * @param n 大于 1 的自然数
 * @return true | false
 */
bool isPrime(int n) {
  // 0 和 1 不是质数 2 和 3 是质数
  if (n <= 3) {
    return n > 1;
  }

  // 方法一：判断一个数能否被小于自身的数整除
  // 时间复杂度：O(n)
  // for (int i = 4; i < n; i++) {
  //   if (n % i == 0) return false;
  // }

  // 方法二：判断一个数能否被小于等于 sqrt(n) 的数整除
  // 时间复杂度：O(sqrt(n))
  // cmath
  // i <= n / i
  for (int i = 4; i * i <= n; i++) {
    if (n % i == 0) return false;
  }

  // 方法三：n > 2 时，只有奇数可能是质数
  // 时间复杂度：O(sqrt(n)/2)
  if (n % 2 == 0) {
    return false;
  }
  // i <= n / i 消除乘法溢出的问题
  for (int i = 4; i <= n / i; i += 2) {
    if (n % i == 0) return false;
  }

  /* 方法四：当 n >= 5 时若为质数，则一定与 6 的倍数相邻 */
  // 时间复杂度：O(sqrt(n)/6)
  // 证明过程：
  // 1. 大于等于 5 的自然数可表示为：{6x-1, 6x, 6x+1, ..., 6x+4}
  // 2. 6x; 6x+2 = 2(3x+1); 6x+3 = 3(2x+1); 6x+4 = 2(3x+2); 均不可能为质数。
  // 3. 当 n>= 5 时若 n 为质数，则必定可写成 6x+1 或 6x-1
  // 若 n 不与 6 的倍数相邻，那么 n 必定不是质数
  if (n % 6 != 1 && n % 6 != 5) {
    return false;
  }
  int max = sqrt(n);
  // 余下的可能性中只需要判断与 6 的倍数相邻的数是否为 n 的因数
  for (int i = 5; i <= max + 1; i += 6) {
    // i -> 6x-1; i+2 -> 6x+1
    if (n % i == 0 || n % (i + 2) == 0) {
      return false;
    }
  }

  // 未找到因数，则 n 为质数
  return true;

  // 方法五：查质数表
  // 时间复杂度：O(1)
  // return prime[n];
}

void getPrime(int n) {
  // 质数筛：质数的整数倍一定是合数
  // - 一个合数可以写成多个质数的乘积，换言之一个合数一定是某个质数的倍数
  // - 那么，当我们明确一个数为质数时，便可将其所有倍数标记为合数
  // 1 为合数，0 为质数，默认为质数
  bool prime[n + 1] = {1, 1, 0};
  // 0 1 2
  // 普通筛
  // for (int i = 2; i <= n; i++) {
  //   if (!prime[i]) {
  //     for (int j = i * 2; j <= n; j += i) {
  //       prime[j] = 1;
  //     }
  //   }
  // }
  // 优化筛
  // for (int i = 2; i <= n; i++) {
  //   if (!prime[i]) {
  //     for (int j = i * i; j <= n; j += i) {
  //       prime[j] = 1;
  //     }
  //   }
  // }
  // 埃式筛
  // 循环终止条件：
  // i * i <= n;
  // int max = sqrt(n); i <= max + 1
  for (int i = 2; i <= n / i; i++) {
    // 如果是质数，则将其所有倍数标记为合数
    if (!prime[i]) {
      for (int j = i * i; j <= n; j += i) {
        prime[j] = 1;
      }
    }
  }

  int count = 0;
  cout << "2-" << n << " 的质数分别为：" << '\n';
  for (int i = 2; i < n; i++) {
    if (!prime[i]) {
      count++;
      cout << i << " ";
    }
  }
  cout << '\n'
       << "质数个数：" << count << endl;
  // 欧拉筛：仅通过最小质因子筛选，避免重复标记
}

#endif